package com.saumil.dsa;

import java.util.Stack;

// http://cslibrary.stanford.edu/110/binarytrees.html#s2
public class BinaryTreePath {

	private boolean elementFound = false;
	private boolean hasPathSumFound = false;
	
	private int maxDepth =  0;
	
	public Node root = null; 
	
	//inner classes
	private static enum TraversalStateEnum {UNINITIALIZED, FIRST_ENTRY, IN_TRAVERSAL, TRAVERSAL_COMPLETE};
	
	private TraversalStateEnum state = TraversalStateEnum.UNINITIALIZED;
	
	public class Node {
		
		public Node left;
		public Node right;
		public int value;
		
		Node()
		{
			left = null;
			right = null;
			value = 0;
		}
		
		Node (Node l, Node r, int v)
		{
			left = l;
			right = r;
			value = v;
		}
		
		@Override
		public boolean equals(Object o) {
			
			if (null != o && o instanceof BinaryTreePath.Node)
			{
				Node n = (Node)o;
				
				if (this.left == n.left && this.right == n.right && this.value == n.value)
					return true;
			}
			return false;
		}
		
		public String toString()
		{
			return (new String("" + value));
		}
	}
	
	public void findPathToNodeFromRoot (Node root, Stack<Node> stack, Node a)
	{
		if (state.ordinal() == TraversalStateEnum.UNINITIALIZED.ordinal())
		{
			if (null == root || null == stack || null == a)
				throw new IllegalArgumentException("Either Root Node or Stack object or Element(node) to be searched is null");
			
		}
		
		elementFound = false;
		
		// Begin Traversal
		findPathFromRoot(root, stack, a);
		state = TraversalStateEnum.TRAVERSAL_COMPLETE;
	}
	
	public void inOrder(Node root)
	{
		if (null == root)
		{
			return;
		}	
		
		inOrder(root.left);
		System.out.println(" "+ root.value + " ");
		inOrder(root.right);
	}
	
	//inOrder traversal : Left-Root-Right
	private void findPathFromRoot(Node root, Stack<Node> stack, Node a )
	{
		
		if (state.ordinal() == TraversalStateEnum.UNINITIALIZED.ordinal())
			state = TraversalStateEnum.FIRST_ENTRY;
		
		else
			state = TraversalStateEnum.IN_TRAVERSAL;
		
		// leaf node
		if (null == root)
		{
			return;
		}
		
		//process Left
		findPathFromRoot(root.left, stack, a);
		
		//visit Node - process Node 
		if (a.value == root.value)
		{
			elementFound = true;
		}
		
		if (elementFound)
		{
			stack.push(root);
			return;
		}
		
		//process Right
		findPathFromRoot(root.right, stack, a);
		
		if (elementFound)
		{
			stack.push(root);
			return; // don't need this return since it's at the end of the function - it is going to return anyways 
		}
	}
	
	public void searchNode (Node root, Node i, Node r)
	{
		if (null == root || null == i)
			return;
		
		if (i.value <= root.value )
			searchNode(root.left, i,r);
		if (root.value == i.value)
			r = root;
		if (i.value > root.value)
			searchNode(root.right, i,r);
		
	}
	
	public Node getInsertionPoint(Node root, Node i)
	{
		if (null == i)
			throw new IllegalArgumentException(i.toString() + " cannot be null!");
		
		if (null == root)
			return null;
		
		Node parent = null;
		Node ptr = root;
		
		while (ptr != null)
		{
			if (i.value <= ptr.value) 
			{
				parent = ptr;
				ptr = ptr.left;
			}
			else 
			{
				parent = ptr;
				ptr = ptr.right;
			}
		}
		
		// you get here when you find a null leaf in the above loop
		return parent;
	}
	
	
	public Node insertNode(Node root, Node i)
	{
		Node iNode = new Node(null,null,i.value);
		Node insertionPoint = getInsertionPoint(root, i);
		
		if (null == insertionPoint)
		{
			insertionPoint = iNode;
			this.root = insertionPoint;
			return insertionPoint;
		}
		
		if (i.value <= insertionPoint.value)
			insertionPoint.left = iNode;
		else
			insertionPoint.right = iNode;
	
		return iNode;
	}
	
	private void countMaxDepth(Node root, int count)
	{
		if (null == root)
			return ;
			
		count++;
		System.out.println("count = " + count);
		if (maxDepth < (count-1)) maxDepth = count;
		countMaxDepth(root.left,count);
		countMaxDepth(root.right,count);
	}
	
	public int maxDepth(Node root)
	{
		maxDepth = 0;
		countMaxDepth(root,0);
		return maxDepth;
	}
	
	//Leftmost element of the root
	public int minValue(Node root)
	{
		if (null == root)
			throw new IllegalArgumentException("Empty Binary tree.");
		
		Node current = root;
		
		while(null != current.left)
			current = current.left;
		
		return current.value;
	}
	
	//Rightmost element of the root
	public int maxValue(Node root)
	{
		if (null == root)
			throw new IllegalArgumentException("Empty Binary tree.");
		
		Node current = root;
		
		while(null != current.right)
			current = current.right;
		
		return current.value;
	}
	
	// Print path from root which has nodes summing up to a given value
	// Using pre-order traversal
	public void hasPathSum(Node root,Stack<Node> s,int sum)
	{
		if (null == root)
			return;
		
		//visit the node
		if (sum != 0) sum -= root.value;
		
		if (sum == 0)
		{
			hasPathSumFound = true;
			s.push(root);
			return;
		}
			
		// process left tree
		hasPathSum(root.left,s,sum);
		
		if (hasPathSumFound)
		{
			s.push(root);
			return;	
		}
		
		// process right tree
		hasPathSum(root.right,s,sum);
		
		if (hasPathSumFound)
		{
			s.push(root);
			return;	
		}
		
	}
	
	public BinaryTreePath constructBinaryTree(int[] a)
	{
		if (null == a)
			throw new IllegalArgumentException("Null input array specified to contructBinaryTree()");
		
		
		BinaryTreePath bt = new BinaryTreePath();
		
		for (int i = 0; i < a.length; i++)
		{	
			BinaryTreePath.Node n = bt.new Node(null,null,a[i]);
			bt.insertNode(bt.root, n);
		}
		
		return bt;
	}
	
	public String getPathFromStack(Stack<Node> s)
	{
		if (null == s)
		{
			throw new IllegalArgumentException("Stack is empty. No path will exist.");
		}
		
		StringBuffer sb = new StringBuffer();
		
		if (s.isEmpty())
		{
			System.out.println("Stack is empty. No path exists.");
		}
		else
		{
			
			while(!s.isEmpty())
			{
				sb.append("-" + s.pop().value);	
			}
		}
		
		return sb.toString();
	}
	
	public boolean isBST(Node root)
	{
		if (null == root)
			return true;
		
		boolean thisNodeCondition = false;
		
		if (root.left != null && root.right != null)
			thisNodeCondition = root.left.value <= root.value && root.right.value > root.value;
		else if (root.right != null)
	    	thisNodeCondition = root.right.value > root.value;
	    else if (root.left != null)	   
	    	thisNodeCondition = root.left.value <= root.value;
	    else
	    	thisNodeCondition = true;
	    	
	    return thisNodeCondition && isBST(root.left) && isBST(root.right);
	}
	
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		int[] a = new int[] {75,50,100,25,75,76,125,12,37,38,87};
		BinaryTreePath bt = new BinaryTreePath();
		Stack<Node> s = new Stack<Node>();
		
		for (int i = 0; i < a.length; i++)
		{	
			BinaryTreePath.Node n = bt.new Node(null,null,a[i]);
			bt.insertNode(bt.root, n);
		}

		System.out.println("MaxDepth of the following BinaryTree is " + bt.maxDepth(bt.root));
		bt.inOrder(bt.root);
		
		System.out.println("MaxValue = " + bt.maxValue(bt.root) +  " MinValue = " + bt.minValue(bt.root) );
		
		System.out.println("isBST() => " + bt.isBST(bt.root));
		
		
		for (int i = 0; i < a.length; i++)
		{	
			BinaryTreePath.Node qNode = bt.new Node(null,null,a[i]); 
			
			s.clear();
			bt.findPathToNodeFromRoot(bt.root, s, qNode);
			
			StringBuffer pathBuffer = new StringBuffer(); // or use StringBuilder - which is Not ThreadSafe but fast 
			
			if (null == s)
				throw new NullPointerException("Stack Empty before building path");
			
			System.out.println("Before popping - pathBuffer = " + pathBuffer.toString());
			
			while (!s.isEmpty())
			{
				pathBuffer.append(s.pop().toString() + "-");
			}
			
			System.out.println("Path From Root to the Node("+ qNode.value+ ") => " + pathBuffer.toString());
		}

		//Print path from root if it has sum matching a given value
		s.clear();
		int sum = 225;
		bt.hasPathSumFound  = false;
		bt.hasPathSum(bt.root, s, sum);
		System.out.println("stack => " + s.toString());
		System.out.println(" Path having sum " + sum + " : " + bt.getPathFromStack(s));
		
	}
	
	
	
}
